package com.sicheng.蓝桥.国赛准备.第10届CPP;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/2 16:10
 */
public class F最优包含 {
    /**
     * 题目给定两个字符串S和T，保证S的长度不小于T的长度，问至少修改S的多少个字符，可以令T成为S的子序列。
     * <p>
     * 输入描述：
     * 两行。
     * 第一行是字符串S，第二行是字符串T。
     * 保证S的长度不小于T的长度，S的长度范围在10~1000之间。
     * <p>
     * 输出描述：
     * 答案，一个非负整数。
     * <p>
     * 输入样例：
     * <p>
     * XBBBBBAC
     * ACC
     * <p>
     * 输出样例：
     * 2
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.next();
        String s2 = scanner.next();
        long[][] dp = new long[s1.length() + 1][s2.length() + 1];

        //初始化起点
        Arrays.fill(dp[0], 1, dp[0].length, Integer.MAX_VALUE);
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (j > i)
                    dp[i][j] = Integer.MAX_VALUE;
                else {
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);
                    }
                }

            }
        }

        System.out.println(dp[s1.length()][s2.length()]);
    }
}
